The invention relates to transforming a stream of respective groups of 2N real input data into a stream of complex output symbols respectively formed of N complex output samples, by interleaved type processing. The invention applies advantageously, but not limitingly, to systems transmitting information coded according to Orthogonal Frequency Division Multiplex (OFDM) coding.
Systems transmitting information using OFDM coding form, for example, the receiving part of a very high speed digital modulation/demodulation device (VDSL modem). In OFDM coding, the signal to be transmitted is coded on N carriers which are phase-modulated and amplitude-modulated as a function of the content of the information to be transmitted. Each carrier has a predetermined frequency and all the frequencies of the carriers are a submultiple of a predetermined sampling frequency. Also, each symbol is formed of N digital carriers, which are N complex samples sampled at the sampling frequency, and must be transformed into a group of 2N real data sampled at twice the sampling frequency. This allows the symbols to be transmitted over a transmission channel, such as a telephone line.
The transformation of a complex symbol respectively formed of N complex samples into a group of 2N real data can be performed in several ways. A first approach performs an inverse Fourier transform of twice the size, i.e., size 2N. However, this approach requires the addition of an extra processing stage as well as the addition of extra memory. A second approach performs an inverse Fourier transform of single size, i.e., size N, followed by a complex filtering. Such an implementation leads to a relatively complicated hardware embodiment.
A third approach also performs an inverse Fourier transform of size N, but is followed by a real filtering. However, this approach, which is simpler to implement than the previous approach, is approximate with regards to the accuracy obtained by reason of a signal/noise ratio which may turn out to be relatively large. A large signal/noise ratio leads to signal degradations. Also, the increase in the performance of this approach, i.e., the reduction in the signal/noise ratio, requires the use of an extremely large real filter. An extremely large real filter involves an expensive hardware implementation.
Another approach includes performing the transformation of the stream of complex symbols respectively formed of N complex samples into a stream of respective groups of 2N real data, by processing of the interleaved type. The theoretical formulation of interleaved type processing is well known to one skilled in the art.
The main characteristics of a processing of the interleaved type are recalled here for all useful purposes. The real signal x(t) corresponding to an OFDM symbol, for example, is defined by formula (I):                               x          ⁡                      (            t            )                          =                              ∑                          k              =              1                                      N              -              1                                ⁢                      xe2x80x83                    ⁢                                    M              k                        ·                          cos              ⁡                              (                                                      2                    ⁢                                          xe2x80x83                                        ⁢                    π                    ⁢                                          xe2x80x83                                        ⁢                                          f                      k                                        ⁢                    t                                    +                                      ϕ                    k                                                  )                                                                        (        I        )            
Mm denotes the amplitude of the carrier of rank k, xcfx86k denotes its phase, fk denotes its frequency, and Nxe2x88x921 is the number of carriers. When the frequencies of the carriers are all multiples of a frequency f1, then formula (I) becomes formula (II) in complex notation:                               x          ⁡                      (            t            )                          =                  Re          ⁡                      [                                          ∑                                  k                  =                  1                                                  N                  -                  1                                            ⁢                              xe2x80x83                            ⁢                                                C                  k                                ·                                  ⅇ                                      2                    ⁢                                          xe2x80x83                                        ⁢                    j                    ⁢                                          xe2x80x83                                        ⁢                    π                    ⁢                                          xe2x80x83                                        ⁢                                          kf                      1                                        ⁢                    t                                                                        ]                                              (        II        )            
in which Ck denotes the complex sample representative of the carrier of rank k. Ck is defined by formula (III):
Ck=Mkxc2x7ejxcfx86kxe2x80x83xe2x80x83(III)
With a sampling of the signal at the frequency Nf1 and by extending the length of the symbol to N carriers (by adding the carrier C0 taken equal to 0), it can then be shown that the N real data of even ranks, corresponding to the N complex samples of the input symbol, are given by formula (IV):                               {                      x                          2              ⁢              p                                }                =                  Re          ⁢                      xe2x80x83                    ⁢                      (                                          IFFT                N                            ⁢                              {                                                      (                                                                  C                        k                                            +                                                                        C                          _                                                                          N                          -                          k                                                                                      )                                    +                                                            j                      ⁡                                              (                                                                              C                            k                                                    -                                                                                    C                              _                                                                                      N                              -                              k                                                                                                      )                                                              ⁢                                          ⅇ                                                                                                    j                            ⁢                                                          xe2x80x83                                                        ⁢                            π                                                    N                                                ⁢                        k                                                                                            }                                      )                                              (        IV        )            
The real data of odd ranks x2p+1 are given by formula (V):                               {                      x                                          2                ⁢                p                            +              1                                }                =                  Im          ⁡                      (                                          IFFT                N                            ⁢                              {                                                      (                                                                  C                        k                                            +                                                                        C                          _                                                                          N                          -                          k                                                                                      )                                    +                                                            j                      ⁡                                              (                                                                              C                            k                                                    -                                                                                    C                              _                                                                                      N                              -                              k                                                                                                      )                                                              ⁢                                          ⅇ                                                                                                    j                            ⁢                                                          xe2x80x83                                                        ⁢                            π                                                    N                                                ⁢                        k                                                                                            }                                      )                                              (        V        )            
In formulas (IV) and (V), {overscore (C)}Nxe2x88x92k represents the complex conjugate of the complex number CNxe2x88x92k, IFFTN represents the xe2x80x9cinverse Fourier transform of size Nxe2x80x9d operator, Im denotes the imaginary part of a complex number, and Re denotes the real part of a complex number. It is therefore seen that the processing of the interleaved type comprises a preprocessing phase in which, for each symbol received formed of N complex samples Ck, a symbol formed of N complex samples AAk is formulated. Each complex sample AAk is defined by formula (VI):
AAk=({overscore (C)}k+CNxe2x88x92k)+j(Ckxe2x88x92{overscore (C)}Nxe2x88x92k)ejxcfx80xcexa/Nxe2x80x83xe2x80x83(VI)
After this preprocessing, a processing phase is performed, which comprises for each symbol formed of the samples AAk an inverse Fourier transform calculation of size N. The result of this inverse Fourier transform is a set of N complex coefficients Ak which, after rearrangement to retrieve the input order, makes it possible to obtain the 2N real data corresponding to the input symbol. This is because the real data of even and odd ranks correspond respectively to the real parts and imaginary parts of the complex samples Ak successively obtained after rearrangement.
Once the 2N real data have been transmitted over the telephone line, they need to be recovered to perform a transformation thereof into a stream of complex symbols so as, in this instance, to obtain the complex carriers Ck. Here again, several approaches are conceivable. A first approach includes performing a direct Fourier transform of twice the size, i.e., size 2N. A second approach includes performing a Fourier transform of single size, i.e., size N, followed by a complex filtering. A third approach also includes performing an inverse Fourier transform of size N, but this time followed by a real filtering.
However, all these approaches have the same drawbacks as those which have been discussed above with regards to the sending part. This is the reason why one preferably performs the transformation of the stream of respective groups of 2N real input data into a stream of complex output symbols formed of N complex output samples by a processing of the interleaved type.
The main characteristics of interleaved type processing performed on reception of the real input data are recalled here for all useful purposes. As made explicit in formula (VII) below:
{Uk}0xe2x89xa6k less than Nxe2x88x921=FFTN{(X2p+jx2pxe2x88x921)0xe2x89xa6p less than Nxe2x88x921}xe2x80x83xe2x80x83(VII)
The notation FFTn denotes the direct Fourier transform operator of size N, and U0 is equal to 0. The initial symbols Ak with p varying from 0 to nxe2x88x921, is defined by a formula (VIII):
Ap=x2p+jx2p+1xe2x80x83xe2x80x83(VIII)
These symbols are formulated in a phase of initial processing.
Each initial complex sample Ap has a real part formed by an input data item of even rank and an imaginary part formed by the succeeding input data item of odd rank. These N initial complex samples are ordered according to a natural order corresponding to the natural order of reception of the input data xp.
The direct Fourier transform calculation of size N then makes it possible to obtain N auxiliary complex samples Uk which are delivered conventionally in a so-called reverse order (bit reverse) with respect to the natural order. These auxiliary samples Uk must thereafter undergo a phase of subsequent processing in accordance with formula (IX) below. This processing includes a rearrangement and a specific processing employing each auxiliary sample Uk and the paired auxiliary sample UNxe2x88x92k, so as to deliver again in the natural order, the N complex output samples Ck. Formula (IX) is as follows:
At present, a known implementation of this interleaved type processing is entirely a software implementation which turns out to be relatively complex to use in industrial apparatus, such as modems, for example. Furthermore, the larger the size of the Fourier transform and the more the processing speed increases, the more severe the implementation constraints become.       (          C      k        )    =            1      4        ⁡          [                        Re          ⁡                      (                          U              k                        )                          +                  Re          ⁡                      (                          U                              N                -                k                                      )                          +                  j          ⁢                      xe2x80x83                    ⁢                      Im            ⁡                          (                              U                K                            )                                      -                  j          ⁢                      xe2x80x83                    ⁢                      Im            ⁡                          (                              U                                  N                  -                  K                                            )                                      +                              ⅇ                                                                                -                    j                                    ⁢                                      xe2x80x83                                    ⁢                  π                                N                            ⁢              K                                ⁡                      (                                          Im                ⁡                                  (                                      U                    K                                    )                                            +                              Im                (                                  U                                      N                    -                    K                                                  )                            -                              j                ⁢                                  xe2x80x83                                ⁢                                  Re                  ⁡                                      (                                          U                                              N                        -                        k                                                              )                                                              +                              j                ⁢                                  xe2x80x83                                ⁢                                  Re                  ⁡                                      (                                          U                      K                                        )                                                                        )                              ]      
An object of the present invention is to reduce the software implementations as far as possible and to use, in particular for the phase of subsequent processing, hardware operators embodied in integrated circuit form and/or in the form of reprogrammable logic circuits including single-access random access memories. These components are readily available, particularly in their simplest form (e.g., as a single-access memory), and are totally independent of the technology used, and are compatible with very high operating frequencies.
Another object of the present invention is to minimize the size of the memories used for the phase of subsequent processing and to optimize the duration of latency of the phase of subsequent processing. The latency is the duration separating the arrival of the first sample of a symbol and the delivery of the first output sample. This is particularly useful for high speed transmission applications such as, for example, VDSL modems operating at 55 mbits/second.
These objects, features and advantages in accordance with the present invention are provided by a process that transforms a stream of respective groups of 2N real input data into a stream of complex output symbols respectively formed of N complex output samples. This transformation is performed by a processing of the interleaved type. This processing comprises, for a current group of input data, a phase of initial processing comprising the formulating of a current initial symbol formed of N current initial complex samples ordered according to a natural order corresponding to the natural order of reception of the input data of the current group. A direct Fourier transform calculation of size N delivers in an order said to be reverse with respect to the natural order N current auxiliary complex samples forming a current auxiliary symbol.
The processing of the interleaved type also comprises a phase of subsequent processing of the current auxiliary symbol in which the N current complex output samples, ordered according to the natural order and forming the current output symbol, are formulated on the basis of the current auxiliary samples delivered. According to a general characteristic of the invention, the phase of subsequent processing of the current auxiliary symbol comprises a first step comprising the sequential storage of the N auxiliary samples in two separately addressable random access memories of respective size equal to N/2, by using a first addressing sequence corresponding to a natural or reverse order.
The phase of subsequent processing of the current auxiliary symbol thereafter comprises a second step. This step comprises the sequential formulation of the N output samples and their sequential delivery in the natural order on the basis of a reading of these N stored auxiliary samples by using a second addressing sequence corresponding to the other of the natural or reverse orders: natural and reverse. Stated otherwise, if during the first step, the two memories have been addressed with an addressing sequence corresponding to the natural order, then the two memories will be addressed in the second step with an addressing sequence corresponding to the reverse order, and vice versa.
Moreover, the phase of subsequent processing of the current auxiliary symbol is temporally nested with the respective phases of subsequent processing of the preceding auxiliary symbol and of the next auxiliary symbol. The addressing of the two memories is performed successively and alternately according to the first and the second addressing sequences. Stated otherwise, the abovementioned temporal nesting signifies that between the end of the delivery of the preceding auxiliary symbol and the end of the delivery of the current auxiliary symbol, the first step (storage) of the phase of subsequent processing of the current auxiliary symbol and the second step (formulation and delivery) of the phase of subsequent processing of the preceding auxiliary symbol are performed.
Likewise, between the end of the delivery of the current auxiliary symbol and the end of the delivery of the next auxiliary symbol, the first step (storage) of the phase of subsequent processing of the next auxiliary symbol, and the second step (formulation and delivery) of the phase of subsequent processing of the current auxiliary symbol are performed. This nesting is regulated by a symbol-clock signal whose frequency is typically on the order of 5 kHz for N=2048. Also, the addressing of the two memories is performed alternately according to the natural order or according to the reverse order with the frequency of the symbol-clock signal.
The invention is noteworthy in that the temporal nesting of the phases of subsequent processing of the various symbols, in combination with the addressing performed alternately according to the natural order and the reverse order, and with the use of two memories (or of two memory banks) of size N/2, makes it possible, for this phase of subsequent processing, to use storage of a size equal to N. In particular, two separately addressable single-access memory banks (or memories) may be used. This would not have been possible if, as is customarily the case for software applications, the rearranging of the auxiliary samples had been performed first followed by the formulating of the output samples.
Indeed, such an implementation combined with the use of single-access memories would have required two memories of size N. One memory is for storing the auxiliary samples of the current auxiliary symbol. The other memory is for storing the auxiliary samples of the preceding symbol on the basis of which the formulating of the output samples in accordance with formula (IX) above would be performed.
According to one mode of implementation of the process, during the first step of the phase of subsequent processing of the current auxiliary symbol, each of the two paired auxiliary samples is stored in a different memory. Also, in the second step, the current output sample of rank k and the paired current output sample of rank Nxe2x88x92k are formulated simultaneously. The current output sample of rank k is delivered directly, whereas the current output sample of rank Nxe2x88x92k is not delivered directly. Indeed, this paired current output sample is stored in one of the memories while awaiting its re-extraction for its subsequent delivery.
The subject of the invention is also directed to a device for transforming a stream of respective groups of 2N real input data into a stream of complex output symbols respectively formed of N complex output samples. This device comprises processing means able to perform on each input group a processing of the interleaved type. These processing means comprise an initial processing block comprising formulation means able to formulate an initial symbol formed of N current initial complex samples ordered according to a natural order corresponding to the natural order of reception of the input data of the input group.
The initial processing block furthermore comprises means of direct Fourier transform calculation of size N, delivering in a so-called reverse order with respect to the natural order, N auxiliary complex samples forming an auxiliary symbol. The processing means furthermore comprises a subsequent processing block able to formulate on the basis of the auxiliary samples delivered, the N complex output samples, ordered according to the natural order, and forming the output symbol corresponding to the input group.
According to a general characteristic of the invention, the subsequent processing block comprises two separately addressable random access memories of respective size equal to N/2. This subsequent processing block furthermore comprises first processing means able to perform a first processing comprising the sequential storage of the N auxiliary samples in the two random access memories according to a first controllable addressing sequence corresponding to one of the orders natural and reverse.
The subsequent processing block also comprises second processing means able to perform a second processing comprising the reading of the N stored auxiliary samples according to a second controllable addressing sequence corresponding to the other of the orders natural and reverse; the sequential formulation of the N output samples; and their sequential delivery in the natural order.
The subsequent processing block also comprises control means able to activate the first processing means, then the second processing means so as to perform successively the first and second processing relating to each current auxiliary symbol; to activate in parallel the first processing means and the second processing means so as to perform respectively the first and second processing relating to two successive auxiliary symbols; and to alternately activate the first and the second addressing sequence with each new activation of the first processing means.